package _06_动态规划;

public class _413_等差数列划分 {

    public static void main(String[] args) {

        _413_等差数列划分 v = new _413_等差数列划分();

        int[] ins = new int[]{1, 2, 3, 4};

        System.out.println(v.numberOfArithmeticSlices(ins));

    }

    // 规律法
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) return 0;
        // 总和计数
        int total = 0;
        // 增量计数
        int add = 0;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i - 1] - nums[i] == nums[i - 2] - nums[i - 1]) {
                total += ++add;
            } else {
                add = 0;
            }
        }
        return total;
    }

    // dp求解等差数列
    public int numberOfArithmeticSlices1(int[] nums) {
        if (nums.length < 3) return 0;
        int len = nums.length;
        // dp[i][j]第i到j项的有多少等差数列
        boolean[][] dp = new boolean[len][len];
        // 总数
        int total = 0;
        // 初始化dp数据
        for (int i = 2; i < len; i++) {
            int start = i - 2;
            // 查看区间是否为等差数列
            if (nums[start + 1] - nums[start] == nums[start + 2] - nums[start + 1]) {
                dp[start][i] = true;
                total++;
            }
        }
        // 等差数列，4项开始计算
        for (int i = len - 3; i >= 0; i--) {
            for (int j = i + 2; j < len; j++) {
                if (dp[i + 1][j] && dp[i][j - 1]) {
                    dp[i][j] = true;
                    total++;
                }
            }
        }
        return total;
    }

}
